Data integrity and authenticity may be fundamental expectations in any secure data communications system, and they comprise an assurance that information has not been modified by someone who is not authorized to do so. In wireless communications scenarios there is a particularly high risk of an adversary intercepting and possibly modifying the communicated data and, thus, a particular need for integrity protection and authentication.
Data integrity may be provided by a Message Authentication Code (MAC). MACs are used for the integrity protection of data communications payload, since they provide a computationally efficient way of protecting even large amounts of data.
MACs are based on a symmetric shared secret between the sender and the receiver. The secret value is called the key. The secret key is one input variable to the MAC calculation and the message to be protected is another input. The MAC calculation results in an integrity check value which is referred to as a tag value. Only somebody who possesses the correct secret key is able to calculate the tag value for any given message. In conventional automatic integrity protection scenarios, the calculated tag value is appended to the message before transmitting the message and the tag value over the communications channel to the recipient. Upon receiving a message protected by a MAC, the receiver calculates a corresponding tag value on the basis of the received data and the shared secret key. If the calculated tag value is equal to the received tag value, the message is accepted as authentic. Examples of known MACs include the so-called Keyed-Hashing for Message Authentication (HMAC) algorithm which is based on cryptographic one-way hash functions such as the secure hash algorithm SHA-1 and the message-digest algorithm MD5.
In manual authentication schemes the calculated tag value is not necessarily appended to the transmitted message. In such a scheme, the tag value may be calculated by the device sending the message and by the device receiving the message. Subsequently, a user compares the calculated tag values or manually transfers a calculated tag value from one device to the other for comparison by that device. Similarly, in some applications, a MAC may be used to perform an integrity check of a data item which was generated by two different devices separately. Hence, in this scenario the data item is not transmitted from a sender to a receiver and, thus, the tag value need not be appended to the data before transmission.
The article “Enhancements to Bluetooth baseband security” by C. Gehrmann and K. Nyberg, Proceedings of Nordsec 2001, Copenhagen, November 2001, describes an example of such a manual authentication scheme of a Diffie-Hellman shared secret that was previously generated by two devices without ever communicating the shared secret via a communications link. The method is based on the assumption that, if a man-in-the-middle is present in the Diffie-Hellman key exchange, the established Diffie-Hellman keys will be different in the legitimate devices. According to this method the generated shared secret is authenticated by manually exchanging a secret key, calculating a tag value of a message authentication code from the generated shared secret and the secret key, and by manually comparing the generated tag values.
In such scenarios involving a user interaction it is desirable to keep the length of the tag value short, in order to make a comparison or a transfer of the tag value by a user feasible, i.e. in order to reduce the time necessary for such a manual comparison and to reduce the risk of errors.
G. Kabatianskii, B. Smeets and T Johansson, “On the cardinality of systematic A-codes via error correcting codes”, IEEE Transaction on Information theory, vol. IT-42, pp. 566-578, 1996, describe the relation between message authentication codes and error correcting codes and disclose a MAC construction based on an error correcting code where the code is partitioned into equivalence classes such that all codewords that differ by a constant are replaced by a singular codeword, thereby generating a new code, the so-called factor code. The tag value is then calculated from a symbol of that factor code on the basis of two keys.